/*
 * @lc app=leetcode.cn id=1219 lang=cpp
 *
 * [1219] 黄金矿工
 */

// @lc code=start
class Solution
{
    int ans = 0;
    int dirs[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

public:
    void dfs(int i, int j, vector<vector<int>> &grid, int golds)
    {
        golds += grid[i][j];
        ans = max(ans, golds);

        int rec = grid[i][j];
        grid[i][j] = 0;

        for (auto [x, y] : dirs)
        {
            int nx = x + i, ny = y + j;
            if (nx < 0 || nx >= grid.size() || ny < 0 || ny >= grid[0].size() || grid[nx][ny] == 0)
            {
                continue;
            }
            dfs(nx, ny, grid, golds);
        }

        grid[i][j] = rec;
    }
    int getMaximumGold(vector<vector<int>> &grid)
    {
        int m = grid.size(), n = grid[0].size();
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                dfs(i, j, grid, 0);
            }
        }

        return ans;
    }
};
// @lc code=end
